package com.xiyou.week01.stack;

import java.util.Stack;

/**
 * 42. 接雨水
 *
 * @ClassName：LeetCode42
 * @Author：西柚
 * @Date：2022/1/6 10:59 下午
 * @Versiion：1.0
 */
public class Trap {

    /**
     * 横着算
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     *
     * @param heights
     * @return
     */
    public static int trap(int[] heights) {
        int ans = 0;
        Stack<Rect> s = new Stack<Rect>();
        for (int height : heights) {
            int accmulatedWidth = 0;
            while (!s.isEmpty() && s.peek().height <= height) {
                int bottom = s.peek().height;
                accmulatedWidth += s.peek().width;
                s.pop();
                if (s.isEmpty()) {
                    // 水从左边流走了
                    continue;
                }
                // 以bottom为底的横块水，最高可以到up（左右两侧可以到min）
                int up = Math.min(height, s.peek().height);
                ans += accmulatedWidth * (up - bottom);
            }
            s.push(new Rect(accmulatedWidth + 1, height));
        }
        return ans;
    }


    static class Rect {
        int width;
        int height;

        Rect(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        System.out.println(trap(nums));
    }

}
